/*
	Name: 
	Copyright: 
	Author: Karamen
	Date: 21/03/14 12:31
	Description: Mo phong thuat toan QuickSort
*/

#include <conio.h>
#include <stdio.h>
#include <math.h>

void PartitionSort(int a[] , int first, int last){
	int key, i, j, k;
	if(first >= last) return ;
	key = a[(first + last) / 2]; 
	i = first;
	j = last;
	do{
			while(a[i] < key) i ++;
			while(a[j] > key) j --;
			if(i <= j){
				int tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
				i++;
				j--;
			}
	}while(i <= j);
		PartitionSort(a,first,j);
		PartitionSort(a,i,last);
}
void QuickSort(int a[], int n){
	PartitionSort(a,0,n-1);
}
void xuatMang(int a[], int n){
	for(int i = 0; i< n; i++){
		printf("\t %d",a[i]);
	}
}
void nhapMang(int a[], int n){
		printf("\nNhap cac phan tu mang: \n");
		for(int i = 0; i < n ; i++){
			printf("A[%d]=",i);
			scanf("%d",&a[i]);
		}
}
int main(){
	int array[50],n;
	printf("Nhap vao kich thuoc mang: ");
	scanf("%d",&n);
	nhapMang(array, n);
	printf("\n Mang vua nhap vao la: \n");
	xuatMang(array,n);
	printf("\n Mang Sau khi sap xep theo QuickSort :\n");
	QuickSort(array,n);
	xuatMang(array,n);
	getch();
}
